package divideAndConquer;

import binaryTree.TreeScan;
import beans.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 不同的二叉搜索树 II
 * 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
 */
public class P95 {
    public List<TreeNode> generateTrees(int n) {
        return generateTree(1, n + 1);
    }

    /**
     * 左闭右开
     */
    public List<TreeNode> generateTree(int begin, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (begin >= end) {//

        } else if (end - begin == 1) {
            TreeNode node = new TreeNode();
            node.val = begin;
            result.add(node);
        } else {// 多个点
            for (int i = begin; i < end; i++) {
                List<TreeNode> left = generateTree(begin, i);
                List<TreeNode> right = generateTree(i + 1, end);
                TreeNode node = null;
                if (left.size() == 0 && right.size() == 0) {
                    node = new TreeNode();
                    node.val = i;
                    result.add(node);
                } else if (left.size() == 0) {
                    for (TreeNode r : right) {
                        node = new TreeNode();
                        node.val = i;
                        node.right = r;
                        result.add(node);
                    }
                } else if (right.size() == 0) {
                    for (TreeNode l : left) {
                        node = new TreeNode();
                        node.val = i;
                        node.left = l;
                        result.add(node);
                    }
                } else {
                    for (TreeNode l : left)
                        for (TreeNode r : right) {
                            node = new TreeNode();
                            node.val = i;
                            node.left = l;
                            node.right = r;
                            result.add(node);
                        }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<TreeNode> treeNodes = new P95().generateTrees(3);
        for (TreeNode node : treeNodes) {
            TreeScan.prevScan(node);
            System.out.println();
        }
    }
}
